package com.wjw.leetcode;

/**
 * fibonacci-number
 * 斐波那契数
 */
public class leetcode509 {

    // 传统递归
    public int fib(int n) {
        return n <= 1 ? n : fib(n - 1) + fib(n - 2);
    }

    // 使用缓存
    public int fib1(int n) {
        int[] memo = new int[n + 1];
        return fib(n, memo);
    }

    public int fib(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] == 0) {
            memo[n] = fib(n - 1) + fib(n - 2);
        }
        return memo[n];
    }

    // 尾递归
    public int fib2(int n) {
        if (n <= 1) {
            return n;
        }

        int a = 0, b = 1, sum = 0;
        while (n-- > 1) {
            sum = a + b;
            a = b;
            b = sum;
        }
        return sum;
    }
}
